# To change this template, choose Tools | Templates
# and open the template in the editor.
#
# todo
#   +function to create sudokus

__author__="martin"
__date__ ="$04.04.2010 12:38:24"

import numpy
import sys

size=9
ok=1
nok=0
pop_size=50
mutation_rate=9
injection_rate=5

class sudoku():
    def __init__(self, parent=None):
        self.parent=parent
        self.stop=0

    def do_stop(self):
        self.stop=1
        
    def create_sudoku(self, num_fields):
        mat=numpy.zeros([size, size])
        n=0
    
        x=numpy.random.randint(size)
        y=numpy.random.randint(size)
        mat[y, x]=numpy.random.randint(size)+1
        #print mat
        mat=self.solve_sudoku_m1(mat)
        if mat!= None:
            while n < (size**2-num_fields):
                x=numpy.random.randint(size)
                y=numpy.random.randint(size)
        
                while (mat[y,x]==0):
                    #print x,y, mat[y,x]
                    x+=1
                    if x >= size:
                        y+=1
                        x=0
                    if y >=size:
                        y=0
                
                mat[y, x]=0
                n+=1
                                   
    
        return mat
    
    def control_row(self, mat, y, x):
        res=1
        for yi in xrange(0, size):
            if yi!=y:
                if mat[yi, x]==mat[y, x]:
                    res=0
        return res
    
    def control_column(self,mat, y, x):
        res=1
        for xi in xrange(0, size):
            if xi!=x:
                if mat[y, xi]==mat[y, x]:
                    res=0
        return res
    
    def control_quadrat(self,mat, y, x):
        res=1
        xbegin=int(x/3)*3
        xend=xbegin+3
        ybegin=int(y/3)*3
        yend=ybegin+3
        for xi in xrange(xbegin, xend):
            for yi in xrange(ybegin, yend):
                if xi!=x or yi!=y:
                    if mat[yi, xi]==mat[y, x]:
                        res=0
        return res
    
    def control_mat(self,mat):
        res=ok
        x=0
        y=0
        while res and x < size and y < size:
            loesungen=range(1, size+1)
            if mat[y, x]== 0.0:
                loesungen=self.check_row(mat, y, x, loesungen)
                loesungen=self.check_column(mat, y, x, loesungen)
                #print loesungen
                loesungen=self.check_quadrat(mat, y, x, loesungen)
                #print loesungen
                if len(loesungen) < 1:
                    #print x,y,mat[y, x],loesungen
                    res=nok
            else:
                if res:
                    res=self.control_row(mat, y,x)
                    if res:
                        res=self.control_column(mat, y, x)
                        if res:
                            res=self.control_quadrat(mat, y, x)
            if res:
                x+=1
                if x>=size:
                    y+=1
                    x=0
        return res, x, y
    
    def error_msg(text):
        print text
    
    def save_sudoku(self,filename, mat):
        try:
    
            file=open(filename, "w")
        except:
            error_msg("could not open file!")
            return nok
        for y in xrange(0, size):
            h=str(int(mat[y, 0]))
            for x in xrange(1, size):
                h+=","+str(int(mat[y, x]))
            h+="\n"
            file.write(h)
        file.close()
        return ok
    
    def load_sudoku(self,filename):
        mat=numpy.zeros([size, size])
        try:
    
            file=open(filename)
        except:
            error_msg("file not found!")
            return mat
        i=0
        for line in file:
            numbers=line.strip().split(",")
            j=0
            for e in numbers:
                mat[i, j]=int(e)
                j+=1
            i+=1
        return mat
    
    def check_row(self,mat, i, j, loesungen):
        n=0
        irange=mat[:,j].nonzero()#only check elements which are non zero
        for n in irange[0]:
            e=mat[n, j]
            if e in loesungen:
                loesungen.remove(e)
        return loesungen
    
    def check_column(self,mat, i, j, loesungen):
        jrange=mat[i,:].nonzero()#only check elements which are non zero
        for n in jrange[0]:
            e=mat[i, n]
            if e in loesungen:
                loesungen.remove(e)
        return loesungen
    
    def check_quadrat(self,mat, i, j, loesungen):
        irange=range(i/3*3, i/3*3+3)
        jrange=range(j/3*3, j/3*3+3)
        for n in irange:
            for m in jrange:
                e=mat[n, m]
                if e in loesungen:
                    loesungen.remove(e)
        return loesungen
    
    def find_empty_cell(self,mat):
        x,y=0,0
        mat_end=0
        while mat[x,y]!=0 and mat_end!=1:
            x+=1
            if x >= size:
                x=0
                if y < size-1:
                    y+=1
                else:
                    x=size-1
                    mat_end=1
    
        if mat_end:
            x=size
            y=size  
        return x,y
    
    def simplify_mat(self,mat):
        ok=1
        rmat=mat.copy()
        psol=range(1,size+1)
        #print "simplify"
        #print rmat
        ok=0
        for i in xrange(0, size):
            for j in xrange(0,size):
                if rmat[i,j]==0:
                    sol=psol[:]
                    sol=check_row(rmat, i,j, sol)
                    sol=check_column(rmat, i,j, sol)
                    sol=check_quadrat(rmat, i, j, sol)
                    if len(sol)==1:
                        rmat[i,j]=sol[0]
                        ok=1
        return rmat
    
    def scan_mat(self,mat):
        rmat=mat.copy()
        psol=range(1,size+1)
        for i in xrange(0, size):
            for j in xrange(0,size):
                if rmat[i,j]==0:
                    sol=psol[:]
                    sol=self.check_row(rmat, i,j, sol)
                    sol=self.check_column(rmat, i,j, sol)
                    sol=self.check_quadrat(rmat, i, j, sol)
                    if len(sol) ==1:
                        rmat[i,j]=sol[0]
                    else:
                        jstart=j/3*3
                        istart=i/3*3
                        n=0
                        ok=1
                        while (n < len(sol)) and (ok):
                            s=sol[n]
                            n+=1
                            srow=range(istart, istart+3)
                            for ic in range(istart, istart+3):
                                if ic != i:
                                    if s in rmat[ic,:]:
                                        srow.remove(ic)
                            scol=range(jstart, jstart+3)
                            for jc in range(jstart, jstart+3):
                                if jc != j:
                                    if s in rmat[:,jc]:
                                        scol.remove(jc)
                            if (len(srow)==1) and (len(scol)==1):
                                rmat[srow[0], scol[0]]=s
                                ok=0
                            elif (len(srow)==1) and (len(scol)>1):
                                nzeros=0
                                for nj in scol:
                                    if mat[srow[0], nj]==0:
                                        nzeros+=1
                                if nzeros==1:
                                    rmat[i, j]=s
                                    ok=0
                            elif (len(scol)==1) and (len(srow)>1):
                                nzeros=0
                                for ni in srow:
                                    if mat[ni, scol[0]]==0:
                                        nzeros+=1
                                if nzeros==1:
                                    rmat[i, j]=s
                                    ok=0
        return rmat
    
    def mat_changed(self,m1, m2):
        m3=abs(m1-m2)
        r=sum(sum(m3))
        return r>0
    
    def search_mat(self, mat):
        #print mat
        ok=1
        while ok:
            omat=mat.copy()
            #mat=simplify_mat(mat)
            mat=self.scan_mat(mat)
            ok=self.mat_changed(mat, omat)
        i,j=self.find_empty_cell_min_sol(mat)
        #print mat
        if self.parent!=None:
            self.parent.inc_progress()
        rmat=None
        if not self.stop:
            if (i < size) and (j < size):
                sol=range(1,size+1)
                sol=self.check_row(mat, i,j, sol)
                sol=self.check_column(mat, i,j, sol)
                sol=self.check_quadrat(mat, i, j, sol)
                if len(sol)==0:
                    rmat=None
                else:
                    rmat=None
                    for s in sol:
                        smat=mat.copy()
                        smat[i,j]=s
                        m=self.search_mat(smat)
                        if m != None:
                            rmat=m
                            break
     
            else:
                rmat=mat

        return rmat
    
    def solve_sudoku_rek(self,omat=numpy.zeros([size, size])):
    
        

                        
        #mat=load_sudoku(fname)
        #print mat
        mat=omat.copy()
        loesungen=range(1, size+1)
        solved=0
        index_l=0
        index_s=0
        min_i=0
        min_j=0
        self.stop=0
        mat_saved=list([])
        if self.parent!=None:
            self.parent.generate_progress_dialog(100)
        pc=0
    
    
            
        mat=self.search_mat( mat)
        solved=1
        if self.stop:
            mat=None
    
        if self.parent!=None:
            self.parent.close_progress_dialog()
        return mat
    
    def find_empty_cell_min_sol(self,mat):
        msol = range(1,size+1)
        mini=size
        minj=size
        for i in range(0, size):
            for j in range(0, size):
                if mat[i,j]==0:
                    sol=range(1, size+1)
                    sol=self.check_row(mat, i,j, sol)
                    sol=self.check_column(mat, i,j, sol)
                    sol=self.check_quadrat(mat, i, j, sol)
                    if len(sol) < len(msol):
                        mini=i
                        minj=j
                        msol=sol
        return mini, minj
                    
    def solve_sudoku_m1(self,omat=numpy.zeros([size, size])):
    
    
                        
        #mat=load_sudoku(fname)
        #print mat
        mat=omat.copy()
        loesungen=range(1, size+1)
        solved=0
        index_l=0
        index_s=0
        min_i=0
        min_j=0
        mat_saved=list([])
        if self.parent!=None:
            self.parent.generate_progress_dialog(100)
        pc=0
        mat=self.scan_mat(mat)   
        n_rounds=0
        self.stop=0
        while not solved and not self.stop:
            n_rounds+=1
            ok=1
            while ok:
                omat=mat.copy()
                #mat=simplify_mat(mat)
                mat=self.scan_mat(mat)
                ok=self.mat_changed(mat, omat)
            i,j=self.find_empty_cell_min_sol(mat)
            if (i >= size) and (j >=size):
                solved=1
            else:
                sol=range(1,size+1)
                sol=self.check_row(mat, i,j, sol)
                sol=self.check_column(mat, i,j, sol)
                sol=self.check_quadrat(mat, i, j, sol)
                
                if len(sol) > 1:
                    d=dict()
                    mat_old=mat.copy()
                    mat[i,j]=sol[0]
                    sol.remove(sol[0])
                    d["mat"]=mat_old
                    d["sol"]=sol
                    d["i"]=i
                    d["j"]=j
                    mat_saved.append(d)
                    #print mat_saved[-1]
                else:
    
                    if len(mat_saved)>0:
                        #print len(mat_saved)
                        
                        while len(mat_saved) > 0 and len(mat_saved[-1]["sol"]) == 0:                         
                            mat_saved.pop()
                        if len(mat_saved)>0:
                            mat=mat_saved[-1]["mat"].copy()
                            i=mat_saved[-1]["i"]
                            j=mat_saved[-1]["j"]
                            sol=mat_saved[-1]["sol"]
                            if len(sol)>0:
                                mat[i,j]=sol[0]
                                sol.remove(sol[0])
                        else:
                            mat=None
                            solved=1
                    else:
                        mat=None
                        solved=1
    
    
             
            #print mat
            if self.parent!=None:
                self.parent.inc_progress()
    
        if self.stop:
            mat=None
        #print "rounds", n_rounds
        if self.parent!=None:
            self.parent.close_progress_dialog()
        return mat
    
    def solve_sudoku_ga(self,omat=numpy.zeros([size, size]), nrounds=100, recombination_method=0, mutation_method=0, select_method=0):
        
        def calc_pop_varianz(pop):
            i =0
            d=0
            for n in xrange(0, len(pop)-1):
                for m in xrange(n+1, len(pop)-1):
                    i+=1
                    d+=sum(sum((pop[n]-pop[m])**2))
            return d/float(i)
            
        def init_pop(omat):
            pop=list()
            for n in xrange(0, pop_size):
                pop.append(omat.copy())
                for x in xrange(0, size):
                    for y in xrange(0, size):
                        if pop[n][x, y]==0:
                            temp=get_random_solution(pop[n], x, y)
                            pop[n][x, y]=temp
            return pop
        
        def get_xy():
            x=numpy.random.randint(0, size)
            y=numpy.random.randint(0, size)
            return x, y
    
        def get_random_solution(mat, x, y):
            l=range(1, size+1)
            l=self.check_row(mat, x, y, l)
    
            if l!=[]:
                if len(l) > 1:
                    n=numpy.random.randint(0, len(l)-1)
                else:
                    n=0
                temp=l[n]
            else:
                temp=numpy.random.randint(1,size)
            return temp
        
        def mutate_mat(omat, mat):
            x, y=get_xy()
            if 0<mat[x,y]<9:
                mat[x,y]+=1
            return mat
                     
        def mutate_mat1(omat, mat):
            x, y=get_xy()
            while omat[x,y]!=0:
                x, y=get_xy()
            temp=get_random_solution(mat, x, y)
    
           
            mat[x, y]=temp
            return mat
        
        def swap_mat(mat, x, y, xn, yn):
            t=mat[x,y]
            mat[x,y]=mat[xn,yn]
            mat[xn,yn]=t
            return mat
            
        def mutate_mat2(omat, mat):
            x, y=get_xy()
            while omat[x,y]!=0:
                x, y=get_xy()
            xn, yn=get_xy()
            n=0
            while (((omat[xn,y]!=0)) or (mat[xn, y]==mat[x,y])) and (n < 10):            
                xn, yn=get_xy()
                n+=1
            #print omat[xn, y],mat[x,y], mat[xn,y],(omat[xn,y]!=0) , (mat[x,y]== mat[xn,y])
            if (omat[xn,y]==0):
                mat=swap_mat(mat, x, y, xn, y)
                
            return mat
           
        def mutate_mat3(omat, mat):
            x, y=get_xy()
            while (omat[x,y]!=0):
                #print unique_list(mat[x,:])
                x, y=get_xy()
            xn, yn=get_xy()
            while (omat[xn,y]!=0):
                xn, yn=get_xy()
            mat=swap_mat(mat, x, y, xn, y)        
            return mat
    
        def mutate_mat4(omat, mat):
            x, y=get_xy()
            while omat[x,y]==0:
                x, y=get_xy()
            temp=numpy.random.randint(1,size)
    
           
            mat[x, y]=temp
            return mat
        
        def mutate_mat5(omat, mat):
            x, y=get_xy()
            while omat[x,y]==0:
                x, y=get_xy()
            temp=mat[x,y]
            if temp < 9:
                temp+=1
            else:
                temp=1
    
           
            mat[x, y]=temp
            return mat    
        
        def mutate_mat6(omat, mat):
            x, y=get_xy()
            while omat[x,y]==0:
                x, y=get_xy()
            temp=numpy.random.randint(1, size)
    
           
            mat[x, y]=temp
            return mat    
    
        def mutate_mat7(omat, mat):
            x, y=get_xy()
            while (omat[x,y]!=0):
                #print len(unique_list(mat[:,y]))
                #print unique_list(mat[x,:])
                x, y=get_xy()
            xn, yn=get_xy()
            n=0
            while ((omat[x,yn]!=0)  or (mat[x,y]==mat[x,yn])) and (n < 10):
                n+=1
                xn, yn=get_xy()
            if omat[x, yn]==0:
                mat=swap_mat(mat, x, y, x, yn)        
            return mat
    
        def mutate_mat8(omat, mat):   
            if numpy.random.randint(1,2)==1:
                m=mutate_mat2(omat, mat)
            else:
                m=mutate_mat7(omat, mat)
            return m   
        
        def select_mutation(nr, omat, mat):
            if (nr==0):
                mat=mutate_mat(omat, mat) 
            elif (nr==1):
                mat=mutate_mat1(omat, mat)
            elif (nr==2):
                mat=mutate_mat2(omat, mat)
            elif (nr==3):
                mat=mutate_mat3(omat, mat)
            elif (nr==4):
                mat=mutate_mat4(omat, mat)    
            elif (nr==5):
                mat=mutate_mat5(omat, mat)
            elif (nr==6):
                mat=mutate_mat6(omat, mat)
            elif (nr==7):
                mat=mutate_mat7(omat, mat)
            elif (nr==8):
                mat=mutate_mat8(omat, mat)
            return mat
                                                                                                    
         
        def score_mat(omat, mat):
            score=0
            for x in xrange(0, size):
                for y in xrange(0, size):
                    if omat[x, y]!=0:
                        if mat[x,y]!=omat[x,y]:
                            score+=1
                    #check rows
                    a=mat[x,:]
                    for n in a:
                        if n==mat[x,y]:
                            score+=1
                    #check columns
                    a=mat[:,y]
                    for n in a:
                        if n==mat[x,y]:
                            score+=1
                    #check quadrats
                    xb=x/3
                    yb=y/3
                    for xn in xrange(xb, xb+3):
                        for yn in xrange(yb, yb+3):
                            if mat[xn, yn]==mat[x,y]:
                                score+=1
                    score-=3
    
            return score
        
        def fac(l):
            e=1
            #print l
            for n in xrange(0, len(l)):
                e*=l[n]
            return e
        
        def score_mat2(mat):
            score=0
            l=numpy.arange(1,size+1)
            l=l.astype(float)
            lf=fac(l)
            for x in xrange(0, size):
                score+=abs(lf-fac(mat[x,:].flatten()))
            for y in xrange(0, size):
               score+=abs(lf-fac(mat[:,y].flatten()))
            for i in xrange(0,3):
               for j in xrange(0,3):
                   score+=abs(lf-fac(mat[i*3:(i+1)*3, j*3:(j+1)*3].flatten()))
            #print score
            return score
        
        def unique_list(l):
            l2=list()
            for e in l:
                if not(e in  l2):
                    l2.append(e)
            return l2
        
        def score_mat3(mat):
            #print mat
            score=0
            l=numpy.arange(1,size+1)
            l=l.astype(float)
            lf=sum(l)
            for x in xrange(0, size):
                score+=abs(lf-sum(mat[x,:].flatten()))
                ms=unique_list(mat[x,:].flatten())
                score+=10*abs(9- len(ms))
            for y in xrange(0, size):
                score+=abs(lf-sum(mat[:,y].flatten()))
                ms=unique_list(mat[:,y].flatten())
                score+=10*abs(9- len(ms))
            for i in xrange(0,3):
               for j in xrange(0,3):
                   score+=abs(lf-sum(mat[i*3:(i+1)*3, j*3:(j+1)*3].flatten()))
                   ms=unique_list(mat[i*3:(i+1)*3, j*3:(j+1)*3].flatten())
                   score+=10*abs(9-len(ms))
            #print score
            return score 
        
        def score_mat5(mat):
            #print mat
            score=0
            for x in xrange(0, size):
                #score+=abs(lf-sum(mat[x,:].flatten()))
                ms=unique_list(mat[x,:].flatten())
                score+=10*abs(9- len(ms))
            for y in xrange(0, size):
                #score+=abs(lf-sum(mat[:,y].flatten()))
                ms=unique_list(mat[:,y].flatten())
                score+=10*abs(9- len(ms))
            for i in xrange(0,3):
               for j in xrange(0,3):
                   #score+=abs(lf-sum(mat[i*3:(i+1)*3, j*3:(j+1)*3].flatten()))
                   ms=unique_list(mat[i*3:(i+1)*3, j*3:(j+1)*3].flatten())
                   score+=10*abs(9-len(ms))
            #print score
            return score 
        
        def score_mat4(mat):
            #print mat
            score=0
            l=numpy.arange(1,size+1)
            l=l.astype(float)
            lf=sum(l)
            for x in xrange(0, size):
                score+=abs(lf-sum(mat[x,:].flatten()))
                ms=unique_list(mat[x,:].flatten())
                score+=10*abs(9- len(ms))
            for y in xrange(0, size):
                score+=abs(lf-sum(mat[:,y].flatten()))
                ms=unique_list(mat[:,y].flatten())
                score+=10*abs(9- len(ms))
                
            return score
        
        def recombination_mat(mat1, mat2):
            a=mat1.copy()
            b=mat2.copy()
    
            x, y=get_xy()
            for i in xrange(0, size):
                for j in xrange(0, size):
                    if i > x:
                        if j > y:
                            a[x, y]=mat2[x,y]
                            b[x, y]=mat1[x,y]
            return a, b
        
        def recombination_mat2(mat1, mat2):
            a=mat1.copy()
            b=mat2.copy()
    
            x, y=get_xy()
            for i in xrange(0, x):
                a[i]=mat2[i]
                b[i]=mat1[i]
            return a, b
        
        def recombination_mat3(mat1, mat2):
            a=mat1.copy()
            b=mat2.copy()
            for x in xrange(0, size):
                for y in xrange(0, size):
                    if numpy.random.uniform() < 0.5:
                        a[x,y]=mat2[x,y]
                        b[x,y]=mat1[x,y]
            return a, b
    
        def recombination_mat4(mat1, mat2):
            #3 point crossover
            a=mat1.copy()
            b=mat2.copy()
            x2=0
            y2=0
            x, y=get_xy()
            while (x2 <= x) and (y2 < y):
                #print x2, y2, x, y
                x2, y2=get_xy()
            for i in xrange(0, size):
                for j in xrange(0, size):
                    if (i > x) and (i < x2):
                        if (j > y) and (j < y2):
                            a[x, y]=mat2[x,y]
                            b[x, y]=mat1[x,y]
            return a, b
        
        
        def select_recombination(nr, mat1, mat2):
            a=mat1
            b=mat2
            if (nr==1):
                a, b=recombination_mat(mat1, mat2)
            elif (nr==2):
                a, b=recombination_mat2(mat1, mat2)
            elif (nr==3):
                a, b=recombination_mat3(mat1, mat2)
            elif (nr==4):
                a, b=recombination_mat4(mat1, mat2)
            return a, b  
                  
        def get_best_score(score):
            b=81*9*8*7*6*5*4*3*2
            bn=0
            for n in xrange(0, len(score)):
                if score[n] < b:
                    b=score[n]
                    bn=n
            return b, bn
        
        def get_worst_score(score):
            b=0
            bn=0
            for n in xrange(0, len(score)):
                if score[n] > b:
                    b=score[n]
                    bn=n
            return b, bn
        
        def calc_fitness(pop, omat):
            s=list()
            for n in xrange(0, len(pop)):
                s.append(score_mat5(pop[n]))
            #print s
            return s
    
        def calc_fitness2(pop, omat,n):
            s=list()
            T=1/float(n)
            k=10**6
            for n in xrange(0, len(pop)):
                s.append(numpy.exp(1*(score_mat5(pop[n]))/(T*k)))
            #print s
            return s
        
        def selection(pop, c_pop, score, c_score, omat):
            #idea only keep parent if his fitness is better than all the childs    
            #print c_pop
            #score=calc_fitness(pop, omat)
            #c_score=calc_fitness(c_pop, omat)
            #print score
            for n in xrange(0, pop_size):
                m=0
                #print score
                cs, ci=get_best_score(c_score)
                if (score[n] > cs):
                    pop[n]=c_pop[m]
                    c_pop.pop(m)
                    score[n]=c_score[m]
                    c_score.pop(m)
              
            best_score, best_ind=get_best_score(score)
            #print best_score
            return pop, score
        
        def selection2(pop, c_pop, score, c_score, omat):
            #idea only keep best parent throw away worst child    
            #score=calc_fitness(pop, omat)
            #c_score=calc_fitness(c_pop, omat)
            bs, bi=get_best_score(score)
            pop[0]=pop[bi]
            score[0]=score[bi]
            ws, wi=get_worst_score(c_score)
            m=0
            for n in xrange(1, pop_size):
                if m!=wi:
                    pop[n]=c_pop[m]
                    score[n]=c_score[m]
                    
                m+=1
                
            #best_score, best_ind=get_best_score(score)
            #print best_score
            return pop, score
        
        def selection3(pop, c_pop, score, c_score, omat):
            #idea only keep best parent throw away worst child    
            #score=calc_fitness(pop, omat)
            #c_score=calc_fitness(c_pop, omat)
            npop=list()
            n_score=list()
            for n in xrange(0, injection_rate):
                bs, bi=get_best_score(score)
                npop.append(pop.pop(bi).copy())
                n_score.append(score.pop(bi))
                
            for n in xrange(injection_rate, pop_size):
                bs, bi=get_best_score(c_score)
                npop.append(c_pop.pop(bi).copy())
                n_score.append(c_score.pop(bi))
            #print len(npop)    
            #best_score, best_ind=get_best_score(score)
            #print best_score
            return npop, n_score
        
        def selection4(pop, c_pop, score, c_score, omat):
            #idea use best children for next generation 
            #score=calc_fitness(pop, omat)
            #c_score=calc_fitness(c_pop, omat)
            npop=list()
            n_score=list()
    
                
            for n in xrange(0, pop_size):
                bs, bi=get_best_score(c_score)
                npop.append(c_pop.pop(bi).copy())
                n_score.append(c_score.pop(bi))
            #print len(npop)    
            #best_score, best_ind=get_best_score(score)
            #print best_score
            return npop, n_score
    
        def selection5(pop, c_pop, score, c_score, omat):
            #idea tournament between children and parent pop
            #score=calc_fitness(pop, omat)
            #c_score=calc_fitness(c_pop, omat)
            npop=list()
            n_score=list()
    
                
            for n in xrange(0, pop_size):
                i=numpy.random.randint(0, len(c_pop)-1)
                #print i, len(c_score)
                if score[n] < c_score[i]:
                    n_ind=pop[n].copy()
                    n_s=score[n]
                else:
                    n_ind=c_pop[i].copy()
                    n_s=c_score[i]
                npop.append(n_ind)
                n_score.append(n_s)
            #print len(npop)    
            #best_score, best_ind=get_best_score(score)
            #print best_score
            return npop, n_score
        
        def choose_select_method(nr, pop, c_pop, score, c_score, omat):
            if (nr==0):
                npop, nscore=selection(pop, c_pop, score, c_score, omat)
            elif (nr==2):
                npop, nscore=selection2(pop, c_pop, score, c_score, omat)
            elif (nr==3):
                npop, nscore=selection3(pop, c_pop, score, c_score, omat)     
            elif (nr==4):
                npop, nscore=selection4(pop, c_pop, score, c_score, omat)
            elif (nr==5):
                npop, nscore=selection5(pop, c_pop, score, c_score, omat)
            return npop, nscore                              
            
        def distance_ind(i, j):
            d=sum(sum((i-j)**2))
        
        numpy.random.seed(0)                        
        pop=init_pop(omat)
        #print pop
        #cpop=init_pop(omat)
        score=calc_fitness(pop, omat)
    
        best_score=size**4
        rounds=0
        if self.parent!=None:
            self.parent.generate_progress_dialog(100)
        pc=0
        while best_score > 0 and rounds < nrounds and not self.stop:
            cpop=list()
            if self.parent!=None:
                self.parent.inc_progress()
    
            for n in xrange(0, pop_size):
                if (rounds%2==0) and (recombination_method > 0):
                   #print "crossover"
                   #print len(cpop), len(pop)
                   d=0
                   while d== 0:
                       m=numpy.random.randint(0, pop_size-1)
                       d=distance_ind(pop[m], pop[n])
                       #print d
                   a, b=select_recombination(recombination_method, pop[n].copy(), pop[m].copy())
                   cpop.append(a)
                   cpop.append(b)
                   #cpop.append(pop[n].copy())
                else:
                   #print "mutation"
                   mn=numpy.random.randint(1,mutation_rate)
                   #print mn
                   c=pop[n].copy()
                   for i in xrange(0, mn):
                       #print cpop[n]
                       c=select_mutation(mutation_method, omat, c)
                   cpop.append(c)
            
            score=calc_fitness(pop, omat)#
            #score=calc_fitness2(pop, omat, rounds+1)
            c_score=calc_fitness(cpop, omat)#
            #c_score=calc_fitness2(cpop, omat, rounds+1)
            #print len(cpop)
            pop, score=choose_select_method(select_method,pop, cpop, score, c_score, omat)
            #print len(pop)
            #print pop[0]
            #score=calc_fitness(pop, omat)
            #print score
            #pop, score=evolve_pop(pop, score)
            
            best_score, best_ind=get_best_score(score)
            best_score=score_mat5(pop[best_ind])
            #pop[0]=pop[best_ind]
            #score[0]=best_score
            if output and rounds%10==0:
                v=calc_pop_varianz(pop)
                print "generation ", rounds, " fitness ", best_score, " varianz ", v
                #print pop[best_ind]
            rounds+=1
            #print rounds
        if self.stop:
            mat=None
        else:
            mat=pop[best_ind]
        if output:
            print "generation ", rounds, " fitness ", best_score
        if self.parent!=None:
            self.parent.close_progress_dialog()
        return mat
                
            
    
                            
    
def test(r):
    s=sudoku()
    mat=s.load_sudoku("sudoku1.txt")
    print mat

    mat=s.solve_sudoku_ga(mat, int(r), 0, 2, 3)
    print mat
    mat=s.load_sudoku("sudoku_106.txt")
    print mat
    mat=s.solve_sudoku_ga(mat, int(r), 4, 2, 3)
    print mat
    mat=s.load_sudoku("sudoku2.txt")
    print mat
    mat=s.solve_sudoku_m1( mat)
    print mat
    mat=s.load_sudoku("sudoku_106.txt")
    mat=s.solve_sudoku_rek( mat)
    print mat

def main(fname):
    mat=solve_sudoku(None, fname)
    print mat

if __name__ == "__main__":
    output=1
    test(500)
else:
    output=0

